package com.clstu.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 会议室问题,贪心算法
 *
 */
public class Meetings {

    public static void main(String[] args) {
        System.out.println("hello".compareTo("world"));
        //测试
        Meet[] mts = new Meet[20];
        for (int i = 0; i < mts.length; i++) {
            mts[i] = new Meet(6+i,6+i+8);
//            System.out.println(i+":  "+mts[i]);
        }
        System.out.println("最多可以举行会议:"+maxMeetings(mts,6));

        //测试最小字典序拼接
        String[] strs = new String[5];
        strs[0]="ba";
        strs[1]="b";
        strs[2]="ba";
        strs[3]="aa";
        strs[4]="ba";
        System.out.println(minDicOrderString(strs));
    }


    //返回最多可以举行的会议的场次,传入会议和会议室开放时间,假设默认18点会议室关闭
    public static int maxMeetings(Meet[] meetings,int openTime){
        //贪心策略,结束时间最早的排前面,
        Arrays.sort(meetings,new MeetComparator());
        int close = 18;//关闭时间
        int cur = openTime;//cur之前表示那段时间已经安排了会议
        int count = 0;//记录可以排的会议的次数
        for(int i=0;i<meetings.length;i++){
            //如果在结束之前
            if(meetings[i].end<=close && meetings[i].start>=cur){
                System.out.println(meetings[i]);
                //cur后移
                cur = meetings[i].end;
                count++;
            }
        }
        return count;
    }

//    //返回最多可以举行的会议的场次,传入会议和会议室开放时间,假设默认18点会议室关闭(暴力法)
//    public static int maxMeetings2(Meet[] meetings,int openTime){
//
//    }

    //编写方法,拼接字符串使其具有最小的字典序(字典上的顺序,贪心策略:a+b<b+a,
    public static String minDicOrderString(String[] strs){
        System.out.println(Arrays.toString(strs));
        Arrays.sort(strs,new DicOrderComparator());
        System.out.println(Arrays.toString(strs));
        //依次拼接之后返回
        StringBuilder res = new StringBuilder();
        for (String str : strs) {
            res.append(str);
        }
        return res.toString();
    }
}
/**
 * 字典序比较器
 */
class DicOrderComparator implements Comparator<String>{
    @Override
    public int compare(String o1, String o2) {
        return (o1+o2).compareTo(o2+o1);
    }
}
/**
 * 会议类
 */
class Meet{
    int start;
    int end;
    //构造器
    public Meet(int s,int e){
        start = s;
        end = e;
    }

    @Override
    public String toString() {
        return "Meet{" +
                "start=" + start +
                ", end=" + end +
                '}';
    }
}
/**
 * 比较器
 */
class MeetComparator implements Comparator<Meet> {
    @Override
    public int compare(Meet o1, Meet o2) {
        return  o1.end - o2.end;
    }
}